﻿using Autodesk.AutoCAD.DatabaseServices;
using Autodesk.AutoCAD.Geometry;
using Autodesk.AutoCAD.Runtime;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CADDemo2025
{
    public class Command0205
    {
        [CommandMethod("Demo0205")]
        public void Demo0205()
        {
            if (!UmUserMethod.SelectEntities(out List<DBPoint> pos, "选择点")) return;
            List<Point3d> points=pos.Select(p=>p.Position).Cast<Point3d>().ToList();
            points = GetConvexHull(points);
            Polyline polyline = new Polyline();
            for (int i = 0; i < points.Count; i++)
            {
                polyline.AddVertexAt(i, new Point2d(points[i].X, points[i].Y), 0, 0, 0);
            }
            polyline.Closed= true;
            polyline.AddEntity();
        }
        public static List<Point3d> GetConvexHull(List<Point3d> points)
        {
            if (points == null || points.Count < 3)
                throw new ArgumentException("At least 3 points are required to form a convex hull.");

            // 按X坐标排序，如果X相同则按Y排序
            var sortedPoints = points.OrderBy(p => p.X).ThenBy(p => p.Y).ToList();

            // 上凸包和下凸包
            var lower = new List<Point3d>();
            var upper = new List<Point3d>();

            foreach (var point in sortedPoints)
            {
                while (lower.Count >= 2 && Cross(lower[lower.Count - 2], lower[lower.Count - 1], point) <= 0)
                    lower.RemoveAt(lower.Count - 1);
                lower.Add(point);
            }

            for (int i = sortedPoints.Count - 1; i >= 0; i--)
            {
                while (upper.Count >= 2 && Cross(upper[upper.Count - 2], upper[upper.Count - 1], sortedPoints[i]) <= 0)
                    upper.RemoveAt(upper.Count - 1);
                upper.Add(sortedPoints[i]);
            }

            // 合并上下凸包，去除最后一个重复的点
            lower.RemoveAt(lower.Count - 1);
            upper.RemoveAt(upper.Count - 1);

            lower.AddRange(upper);
            return lower;
        }

        private static double Cross(Point3d O, Point3d A, Point3d B)
        {
            return (A.X - O.X) * (B.Y - O.Y) - (A.Y - O.Y) * (B.X - O.X);
        }

    }
}
